package com.wrial.kind.linkedList;
/*
 * @Author  Wrial
 * @Date Created in 22:56 2020/8/7
 * @Description
 *  给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
    k 是一个正整数，它的值小于或等于链表的长度。
    如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
    给你这个链表：1->2->3->4->5
    当 k = 2 时，应当返回: 2->1->4->3->5
    当 k = 3 时，应当返回: 3->2->1->4->5
 */

import java.util.List;

public class ReverseKGroup {

    /**
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        ListNode ans = new ListNode(-1);
        ListNode pre = ans, start = head, end = head, after;

        while (start != null) {
            for (int i = 0; i < k - 1 && end != null; i++) {
                end = end.next;
            }
            if (end == null) break;

            after = end.next;
            end.next = null;
            end = start;
            start = reverse(start);

            pre.next = start;
            end.next = after;  // 一定要连接回来不然就GG

            pre = end;
            start = after;
            end = after;
        }
        return ans.next;


    }

    private ListNode reverse(ListNode start) {

        ListNode newHead = null;
        while (start != null) {
            ListNode nextStart = start.next;
            start.next = newHead;
            newHead = start;
            start = nextStart;
        }
        return newHead;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
